package Rpn;

import java.util.regex.Pattern;

//逆波兰算法
public class Rpn {

    private Stack opera;
    private Stack num;

    public Rpn()
    {

        this.opera = new Stack(100);
        this.num = new Stack(100);
    }

    public int calculate(String equation)
    {
        //将中缀表达式转化为后缀表达式
        equation = this.toRpnEquation(equation);

        //将后缀表达式转化成一个数组，每个元素是一个操作结点
        String[] equationArray = equation.split(" ");

        //通过后缀表达式进行计算
        for (String chunk : equationArray) {
            if (chunk.matches("\\d+")) {
                this.num.push(chunk);
            } else {
                if (this.num.isEmpty()){
                    System.out.println("后缀表达式出错了："+chunk);
                    break;
                }
                int num1 = Integer.parseInt(this.num.pop());
                if (this.num.isEmpty()){
                    System.out.println("后缀表达式出错了："+chunk);
                    break;
                }
                int num2 = Integer.parseInt(this.num.pop());
                int result;
                switch (chunk) {
                    case "+":
                        result = num1 + num2;
                        break;
                    case "-":
                        result = num2 - num1;
                        break;
                    case "*":
                        result = num2 * num1;
                        break;
                    case "/":
                        result = num2 / num1;
                        break;
                    default:
                        System.out.println("出错了，未知的计算操作式："+chunk);
                        result = 0;
                        break;
                }
                this.num.push(String.valueOf(result));
            }
        }
        return Integer.parseInt(this.num.pop());
    }

    /**
     * 将中缀表达式转化为后缀表达式
     * 1. 从左往右扫描中缀表达式
     * 2. 如果是数字那么将其直接入栈到数组num中
     * 3. 如果是操作，需要进一步判断
     * a.   如果是左括号'('直接入栈到数组opera中
     * b1.  如果是运算符（'+'、'-'、'*'、'/'），先判断数组opera的栈顶的操作数的优先级（如果是空栈那么直接入栈到数组opera），
     * b2.  如果是左括号那么直接入栈到数组opera中，
     * b3.  如果栈顶是运算符，且栈顶运算符的优先级大于等于该运算符.那么将栈顶的运算符出栈，并入栈到数组num中，重复步骤3，
     * b4.  如果栈顶运算符优先级小于该运算符，那么直接将该运算符入栈到opera中
     * c.   如果是右括号')'，那么说明在opera数组中一定有一个左括号与之对应（在你没输错的情况下），那么将opera中的运算符依次出栈，并入栈到num中，直到遇到左括号'('（注意左括号不用入栈到num）
     * 4. 如果中缀表达式扫描完了，那么将opera中的操作数依次出栈，并入栈到num中就可以了，如果没有没有扫描完重复1-3步
     *
     * @param equation String
     *
     * @return String
     **/
    protected String toRpnEquation(String equation)
    {
        String[] equationArray;
        String chunk;

        //数字栈
        Stack num = new Stack(100);

        //操作符栈
        Stack opera = new Stack(100);

        while (equation.length() > 0) {
            equationArray = this.fetchChunk(equation);
            chunk = equationArray[0];
            if (chunk.matches("\\d+")) {
                num.push(chunk);
            } else {
                switch (chunk) {
                    case "(":
                        opera.push(chunk);
                        break;
                    case "+":
                    case "-":
                    case "*":
                    case "/":
                        while (true) {
                            if (opera.isEmpty()) {
                                opera.push(chunk);
                                break;
                            } else if ("(" == opera.peek()) {
                                opera.push(chunk);
                                break;
                            } else if (this.level(opera.peek()) >= this.level(chunk)) {
                                String op = opera.pop();
                                num.push(op);
                            } else {
                                opera.push(chunk);
                                break;
                            }
                        }
                        break;
                    case ")":
                        while (true) {
                            String top = opera.pop();
                            if (top.equals("(")) {
                                break;
                            }
                            num.push(top);
                        }
                        break;
                }
            }
            equation = equationArray[1];
        }

        //将opera栈中的数据全部插入到num栈中
        while (!opera.isEmpty()) {
            num.push(opera.pop());
        }

        String rpnEquation = "";
        while (!num.isEmpty()) {
            rpnEquation = num.pop() + " " + rpnEquation;
        }
        return rpnEquation;
    }

    /**
     * 返回一个操作符的优先级
     *
     * @param operator int 操作符
     *
     * @return int
     **/
    protected int level(String operator)
    {
        int level = 0;
        switch (operator) {
            case "+":
            case "-":
                level = 1;
                break;
            case "*":
            case "/":
                level = 2;
                break;
            default:
                level = 0;
                break;
        }
        return level;
    }


    /**
     * 取出一个单元
     *
     * @param equation String[] 表达式
     *
     * @return String[]
     **/
    protected String[] fetchChunk(String equation)
    {
        if (0 == equation.length()) {
            return null;
        }
        String chunk = equation.substring(0, 1);
        equation = equation.substring(1);
        if (chunk.matches("\\d+")) {
            while (equation.length() > 0) {
                if (equation.substring(0, 1).matches("\\d+")) {
                    chunk = chunk + equation.substring(0, 1);
                    equation = equation.substring(1);
                } else {
                    break;
                }
            }
        }

        String[] result = new String[2];
        result[0] = chunk;
        result[1] = equation;
        return result;
    }


    //栈
    protected class Stack {

        private int max;
        private String[] data;
        private int top = -1;

        public Stack(int max)
        {
            this.max = max;
            this.data = new String[max];
        }

        /**
         * 数据入栈
         *
         * @param value String 入栈的数据
         *
         * @return void
         **/
        public void push(String value)
        {
            if (this.isFull()) {
                throw new RuntimeException("栈已满");
            }
            this.data[++this.top] = value;
        }

        /**
         * 数据出栈
         *
         * @return String
         **/
        public String pop()
        {
            if (this.isEmpty()) {
                return null;
            }
            String value = this.data[this.top--];
            return value;
        }

        /**
         * 偷看一下栈顶数据
         *
         * @return String
         **/
        public String peek()
        {
            if (this.isEmpty()) {
                return null;
            }
            return this.data[this.top];
        }

        /**
         * 判断是否为空
         *
         * @return boolean
         **/
        public boolean isEmpty()
        {
            return this.top == -1;
        }

        /**
         * 判断是否已满
         *
         * @return boolean
         **/
        protected boolean isFull()
        {
            return (this.top + 2) == this.max;
        }
    }
}
